package gold.digger;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC46 {

    public List<List<Integer>> permute(int[] nums) {
        List<Integer> arr = makeList(nums, 0, nums.length - 1);
        return new ArrayList<>(permuteRecur(arr));
    }

    public Set<List<Integer>> permuteRecur(List<Integer> arr) {
        Set<List<Integer>> per = new HashSet<>();
        if (null == arr || arr.size() <= 0) {
            return per;
        }

        if (arr.size() == 1) {
            per.add(arr);
            return per;
        }

        for (int i = 0; i < arr.size(); ++i) {
            List<Integer> subList = deepCopyList(arr, i);
            Set<List<Integer>> subPer = permuteRecur(subList);
            for (List<Integer> subPerELe : subPer) {
                List<Integer> tempPerBefore = new ArrayList<>();
                List<Integer> tempPerAfter = new ArrayList<>();
                tempPerBefore.add(arr.get(i));//add before
                tempPerBefore.addAll(subPerELe);

                tempPerAfter.addAll(subPerELe); //add after
                tempPerAfter.add(arr.get(i));

                per.add(tempPerBefore);
                per.add(tempPerAfter);
            }
        }

        return per;
    }

    public List<Integer> makeList(int[] arr, int start, int end) {
        List<Integer> intList = new ArrayList<>();
        for (int i = start; i <= end; ++i) {
            intList.add(arr[i]);
        }
        return intList;
    }

    public List<Integer> deepCopyList(List<Integer> list, int ignoreIndex) {
        List<Integer> subList = new ArrayList<>();
        for (int i = 0; i < list.size(); ++i) {
            if (i == ignoreIndex) {
                continue;
            }
            subList.add(list.get(i));
        }
        return subList;
    }

    public static void main(String[] args) {
        LC46 an = new LC46();
        int[] arr = {1, 2, 3};

        System.out.println(an.permute(arr));
    }
}
